from typing import List


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # 获取长宽高
        height = len(grid)
        length = len(grid[0])
        if height == 0 or length == 0:
            return 0
        # 初始化dp数组
        dp = [[0 for _ in range(length)] for _ in range(height)]

        # 从左向右开始遍历
        for i in range(height):
            for j in range(length):
                if i == 0 and j == 0:  # 初始化起点
                    dp[i][j] = grid[i][j]
                else:
                    if i == 0:  # 处理非起点的第一行
                        dp[i][j] = dp[i][j-1]+grid[i][j]
                    elif j == 0:  # 处理非前点的第一列
                        dp[i][j] = dp[i-1][j]+grid[i][j]
                    else:  # 处理上方左方都有来源的普通情况
                        dp[i][j] = min(dp[i][j-1], dp[i-1][j])+grid[i][j]
        return dp[-1][-1]  # dp每一项的值，即是到达改点的最短距离，返回dp最后一项即使要求的答案


if __name__ == "__main__":
    mySol = Solution()
    myGrid = [[1, 3, 1],
              [1, 5, 1],
              [4, 2, 1]]
    out = mySol.minPathSum(grid=myGrid)
    print(out)
